﻿/************************************************************************

   Extended Silverlight Toolkit

   Copyright (C) 2010-2012 Xceed Software Inc.

   This program is provided to you under the terms of the Microsoft Public
   License (Ms-PL) as published at http://extendedsilverlight.codeplex.com/license

   Please purchase a commercial version of this toolkit if you are using
   it in a commercial product. The commercial versions support the project,
   and also include more features for each control, priority support,
   source code, updates, removed watermark, and a proprietary license.

   Visit http://xceed.com and follow @datagrid on Twitter.

  **********************************************************************/

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;
using Xceed.Silverlight.Data.Stats;

namespace Xceed.Silverlight.Data
{
  public sealed class ListDataSourceProvider : SyncDataSourceProvider
  {
    #region Static Fields

    private const int MaximumIndexCount = 3;

    #endregion

    #region Constructor

    public ListDataSourceProvider( IEnumerable dataSource )
    {
      if( dataSource == null )
        throw new ArgumentNullException( "dataSource" );

      m_originalDataSource = dataSource;

      DataSourceCollection dataSourceCollection = new DataSourceCollection( dataSource );
      m_collection = new ListDataItemCollection( dataSourceCollection );
    }

    #endregion

    #region CanSkip Property

    public override bool CanSkip
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanFilter Property

    public override bool CanFilter
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanJumpToItem Property

    public override bool CanJumpToItem
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanJump Property

    public override bool CanJump
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanFilterGroup Property

    public override bool CanFilterGroup
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanCount Property

    public override bool CanCount
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanGroupCount Property

    public override bool CanGroupCount
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region CanCalculateStats Property

    public override bool CanCalculateStats
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region ElementType Property

    protected internal override Type ElementType
    {
      get
      {
        return m_collection.ElementType;
      }
    }

    #endregion

    #region CanFilterPredicate Property

    internal override bool CanFilterPredicate
    {
      get
      {
        return true;
      }
    }

    #endregion

    #region DataSource Property

    internal IEnumerable DataSource
    {
      get
      {
        return m_originalDataSource;
      }
    }

    #endregion

    protected override void Initialize()
    {
      base.Initialize();

      // Listen to collection notifications.
      m_collection.CollectionChanged += new NotifyCollectionChangedEventHandler( this.OnNotifyCollectionChanged );
      m_collection.ItemChanged += new EventHandler<ItemChangedEventArgs>( this.OnNotifyItemChanged );
    }

    protected override IEnumerable<SortDescription> GetPrimaryKeyInfo()
    {
      yield return m_collection.PrimaryKeyInfo.Field;
    }

    protected override CountQueryResult ExecuteCountQuery( CountQueryParameters queryParameters )
    {
      CountQueryResult queryResult;

      if( this.TryHandleSingleItemCountQuery( queryParameters, out queryResult ) )
        return queryResult;

      return this.HandleRegularCountQuery( queryParameters );
    }

    protected override DataQueryResult ExecuteDataQuery( DataQueryParameters queryParameters )
    {
      DataQueryResult queryResult;

      if( this.TryHandleSingleItemDataQuery( queryParameters, out queryResult ) )
        return queryResult;

      return this.HandleRegularDataQuery( queryParameters );
    }

    protected override GroupCountQueryResult ExecuteGroupCountQuery( GroupCountQueryParameters queryParameters )
    {
      GroupCountQueryResult queryResult;

      if( this.TryHandleSingleItemGroupCountQuery( queryParameters, out queryResult ) )
        return queryResult;

      return this.HandleRegularGroupCountQuery( queryParameters );
    }

    protected override StatQueryResult ExecuteStatQuery( StatQueryParameters queryParameters )
    {
      Debug.Assert( ( queryParameters.Function != null )
                 && ( queryParameters.Function.StatFunction != null ) );

      StatQueryResult queryResult;

      if( this.TryHandleSingleItemStatQuery( queryParameters, out queryResult ) )
        return queryResult;

      return this.HandleRegularStatQuery( queryParameters );
    }

    protected override IEnumerable<Type> GetSupportedStatFunctions( Type dataType )
    {
      if( dataType == null )
        yield break;

      yield return typeof( StatFunction );
    }

    protected override void OnInvalidateData()
    {
      m_collection.Reset();
    }

    protected override void OnInvalidateDataObjects( IEnumerable<ItemChangedDescription> itemsChanged )
    {
      this.OnItemsChanged( itemsChanged );
    }

    protected override void OnDataObjectsAdded( IEnumerable<object> itemsAdded )
    {
      m_collection.Synchronize();
    }

    protected override void OnDataObjectsRemoved( IEnumerable<object> itemsRemoved )
    {
      m_collection.Synchronize();
    }

    internal override bool IsStatFunctionSupportedNatively( StatFunction statFunction )
    {
      if( ( statFunction == null ) || ( !statFunction.RequiresAccumulation ) )
        return false;

      StatFunction[] prerequisiteFunctions = statFunction.PrerequisiteFunctions;

      return ( prerequisiteFunctions == null )
          || ( prerequisiteFunctions.Length <= 0 );
    }

    internal override bool FindElementMemberType( string memberName, out Type type )
    {
      ListDataItemPrimaryKeyDescription primaryKeyInfo = m_collection.PrimaryKeyInfo;
      if( memberName == primaryKeyInfo.Field.PropertyName )
      {
        type = primaryKeyInfo.Type;
        return true;
      }

      return base.FindElementMemberType( memberName, out type );
    }

    internal override bool TryWrapDataObject( object item, out RawDataItem dataItem )
    {
      dataItem = item as RawDataItem;
      if( dataItem != null )
        return true;

      return this.TryGetItem( item, out dataItem );
    }

    internal override bool TryUnwrapLayer( RawDataItem dataItem, out object item )
    {
      item = dataItem;

      return ( dataItem != null );
    }

    private ListDataItemEnumerable GetDataItems(
      DataQueryParameters queryParameters,
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder,
      bool reverseOrder )
    {
      if( index == null )
        throw new ArgumentNullException( "index" );

      if( sortOrder == null )
        throw new ArgumentNullException( "sortOrder" );

      // Set the query parameters to start at a precise item.
      ListDataItemEnumerable enumerable;
      if( queryParameters.ItemJump != null )
      {
        RawDataItem startingItem = queryParameters.ItemJump.Item as RawDataItem;
        if( startingItem == null )
          throw new DataInternalException( "An attempt was made to jump to an unknown item." );

        IEnumerable<object> memberValues = ListDataSourceProvider.GetMemberValues( startingItem, sortOrder );

        enumerable = index.GetDataItems( memberValues, reverseOrder );
      }
      // Set the query parameters to start at a precise group or item.
      else if( queryParameters.Jump != null )
      {
        JumpRequest jumpRequest = queryParameters.Jump;
        JumpStartPosition startPosition = jumpRequest.StartPosition;
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );
        bool includeStartingItem = ( startPosition == JumpStartPosition.Before );

        enumerable = index.GetDataItems( jumpValues, reverseOrder, !includeStartingItem );
      }
      // Set the query parameters to start on the first or last item.
      else
      {
        enumerable = index.GetDataItems( reverseOrder );
      }

      return enumerable;
    }

    private IEnumerable<long> GetGroupCount(
      JumpRequest jumpRequest,
      FilterGroupRequest filterGroupRequest,
      ListDataItemIndex index,
      int levelCount,
      bool reverseOrder )
    {
      if( index == null )
        throw new ArgumentNullException( "index" );

      IEnumerable<int> groupCount;

      if( ( jumpRequest != null ) && ( filterGroupRequest != null ) )
      {
        JumpStartPosition startPosition = jumpRequest.StartPosition;
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );
        bool includeStartingItem = ( startPosition == JumpStartPosition.Before );
        IEnumerable<object> groupValues = ListDataSourceProvider.GetFilterGroupValues( filterGroupRequest.Values );

        groupCount = index.GetGroupCount(
                       levelCount,
                       groupValues,
                       jumpValues,
                       reverseOrder,
                       !includeStartingItem );
      }
      // Count every group from a starting position.
      else if( jumpRequest != null )
      {
        JumpStartPosition startPosition = jumpRequest.StartPosition;
        IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );
        bool includeStartingItem = ( startPosition == JumpStartPosition.Before );

        groupCount = index.GetGroupCount(
                       levelCount,
                       jumpValues,
                       reverseOrder,
                       !includeStartingItem );
      }
      // Count the children of a specific group.
      else if( filterGroupRequest != null )
      {
        IEnumerable<object> groupValues = ListDataSourceProvider.GetFilterGroupValues( filterGroupRequest.Values );

        groupCount = index.GetGroupCount( levelCount, groupValues );
      }
      // Count every group.
      else
      {
        groupCount = index.GetGroupCount( levelCount );
      }

      return ( from count in groupCount
               select Convert.ToInt64( count ) );
    }

    private ListDataItemIndex GetIndex( FilterRequest filterRequest )
    {
      Predicate<object> filter;
      FilterExpressionBase filterExpression;

      ListDataSourceProvider.GetFilter( filterRequest, out filter, out filterExpression );

      return this.GetIndex( null, null, filter, filterExpression, true );
    }

    private ListDataItemIndex GetIndex(
      SortRequest sortRequest,
      FilterRequest filterRequest,
      bool allowSubset,
      out bool reversedOrder )
    {
      reversedOrder = false;

      if( sortRequest == null )
        return this.GetIndex( filterRequest );

      // Retrieve the sort order.
      IList<SortDescription> sortOrder = sortRequest.SortDescriptions;
      IComparer comparer = new NullComparer( new DefaultComparer() );
      IEnumerable<IComparer> comparers = Enumerable.Repeat( comparer, sortOrder.Count );

      // Retrieve the filter.
      Predicate<object> filter;
      FilterExpressionBase filterExpression;
      ListDataSourceProvider.GetFilter( filterRequest, out filter, out filterExpression );

      // Get the appropriate index for the task.
      ListDataItemIndex index = this.GetIndex( sortOrder, comparers, filter, filterExpression, allowSubset );
      reversedOrder = ListDataSourceProvider.IsSortOrderReversed( index, sortOrder );

      return index;
    }

    private ListDataItemIndex GetIndex(
      IEnumerable<SortDescription> sortOrder,
      IEnumerable<IComparer> groupValueComparers,
      Predicate<object> filter,
      FilterExpressionBase filterExpression,
      bool allowSubset )
    {
      // Check if an existing index match the requirements.
      LinkedListNode<ListDataItemIndex> node = m_indexes.First;
      while( node != null )
      {
        ListDataItemIndex index = node.Value;
        ListDataItemIndexConfiguration configuration = index.Configuration;

        // Check out if the filtering applied on the index matches.
        if( ( configuration.Filter == filter ) && ( configuration.FilterExpression == filterExpression ) )
        {
          // Check out if the index can be use for the given sort order.
          if( ( sortOrder == null )
            || ( allowSubset && ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder ) )
            || ( !allowSubset && ListDataSourceProvider.IsExactSortOrder( index, sortOrder ) ) )
          {
            // Move the selected index closer to the first index in order to find it quicker next time.
            if( node.Previous != null )
            {
              LinkedListNode<ListDataItemIndex> previousIndex = node.Previous;
              m_indexes.Remove( index );
              m_indexes.AddBefore( previousIndex, index );
            }

            return index;
          }
        }

        // Check out the next index;
        node = node.Next;
      }

      // Free up old indexes.
      while( ( m_indexes.Count >= ListDataSourceProvider.MaximumIndexCount ) && ( m_indexes.Count > 0 ) )
      {
        m_indexes.RemoveLast();
      }

      List<IComparer> newGroupValueComparers = new List<IComparer>();
      if( groupValueComparers != null )
      {
        newGroupValueComparers.AddRange( groupValueComparers );
      }

      List<SortDescription> newSortOrder = new List<SortDescription>();
      if( sortOrder != null )
      {
        newSortOrder.AddRange( sortOrder );
      }

      // Make sure the primary key fields are included in the sort.
      if( ( allowSubset ) || ( newSortOrder.Count <= 0 ) )
      {
        foreach( SortDescription pk in this.PrimaryKeyInfo )
        {
          // It is useless to include the same field twice.
          if( newSortOrder.Select( ( item ) => item.PropertyName ).Contains( pk.PropertyName ) )
            continue;

          newSortOrder.Add( pk );
          newGroupValueComparers.Add( new NullComparer( new DefaultComparer() ) );
        }
      }

      // Create a new index that will fit the given configuration.
      ListDataItemIndexConfiguration newConfiguration = new ListDataItemIndexConfiguration(
                                                          newSortOrder,
                                                          newGroupValueComparers,
                                                          filter,
                                                          filterExpression,
                                                          m_collection.ElementType,
                                                          this.GetElementMemberType );
      ListDataItemIndex newIndex = new ListDataItemIndex( m_collection, newConfiguration );
      m_indexes.AddFirst( newIndex );

      return newIndex;
    }

    private static IEnumerable<RawDataItem> Skip(
      IEnumerable<RawDataItem> dataItems,
      SkipRequest request,
      ItemJumpRequest startPosition )
    {
      long skipCount = ( request != null ) ? request.Count : 0;

      if( ( startPosition != null ) && ( skipCount > 0 ) )
      {
        IEnumerator<RawDataItem> enumerator = dataItems.GetEnumerator();

        if( enumerator.MoveNext() )
        {
          // The expected starting item doesn't exists.  We must adjust the
          // skip count accordingly.
          if( !object.Equals( enumerator.Current, startPosition.Item ) )
          {
            skipCount--;
          }
        }
      }

      while( skipCount > 0 )
      {
        int count = ( skipCount > int.MaxValue )
                      ? int.MaxValue
                      : Convert.ToInt32( skipCount );
        dataItems = dataItems.Skip( count );
        skipCount -= count;
      }

      return dataItems;
    }

    private static IEnumerable<RawDataItem> Take(
      IEnumerable<RawDataItem> dataItems,
      TakeRequest request )
    {
      if( request != null )
      {
        dataItems = dataItems.Take( request.Count );
      }

      return dataItems;
    }

    private static void GetFilter(
      FilterRequest request,
      out Predicate<object> filter,
      out FilterExpressionBase filterExpression )
    {
      if( request != null )
      {
        filter = request.Filter;
        filterExpression = request.Expression;
      }
      else
      {
        filter = null;
        filterExpression = null;
      }
    }

    private static bool IsExactSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder )
    {
      bool reversed;
      return ListDataSourceProvider.IsExactSortOrder( index, sortOrder, out reversed );
    }

    private static bool IsSubsetSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder )
    {
      bool reversed;
      return ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder, out reversed );
    }

    private static bool IsExactSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder,
      out bool reversed )
    {
      reversed = false;

      return ( ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder, out reversed ) )
          && ( index.Configuration.SortOrder.Count == sortOrder.Count() );
    }

    private static bool IsSubsetSortOrder(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder,
      out bool reversed )
    {
      reversed = false;

      IList<SortDescription> indexSortOrder = index.Configuration.SortOrder;
      if( indexSortOrder.Count <= 0 )
        return !sortOrder.Any();

      Nullable<bool> isReversed = null;
      int i = 0;

      foreach( SortDescription sort in sortOrder )
      {
        if( i >= indexSortOrder.Count )
          return false;

        SortDescription indexSort = indexSortOrder[ i ];
        if( sort.PropertyName != indexSort.PropertyName )
          return false;

        bool oppositeOrder = ( sort.Direction != indexSort.Direction );
        if( isReversed.HasValue )
        {
          // The index isn't sorted in appropriate order.
          if( oppositeOrder != isReversed.Value )
            return false;
        }
        else
        {
          isReversed = oppositeOrder;
        }

        i++;
      }

      reversed = isReversed.GetValueOrDefault( false );
      return true;
    }

    private static bool IsSortOrderReversed(
      ListDataItemIndex index,
      IEnumerable<SortDescription> sortOrder )
    {
      bool reversed;
      ListDataSourceProvider.IsSubsetSortOrder( index, sortOrder, out reversed );

      return reversed;
    }

    private static IEnumerable<object> GetMemberValues(
      RawDataItem dataItem,
      IEnumerable<SortDescription> sortOrder )
    {
      return ( from sort in sortOrder
               select dataItem.GetDataMemberValue( sort.PropertyName ) );
    }

    private static IEnumerable<object> GetJumpValues( IEnumerable<JumpValue> values )
    {
      foreach( JumpValue jumpValue in values )
      {
        yield return jumpValue.Value;
      }
    }

    private static IEnumerable<JumpValue> CreateJumpValues( IEnumerable<object> values )
    {
      foreach( object value in values )
      {
        yield return new JumpValue( value );
      }
    }

    private static StatResult GetStatResult(
      StatFunction statFunction,
      IEnumerable<RawDataItem> dataItems,
      long count )
    {
      IEnumerator<RawDataItem> enumerator = dataItems.GetEnumerator();

      try
      {
        for( long i = 0; ( enumerator.MoveNext() ) && ( i < count ); i++ )
        {
          RawDataItem dataItem = enumerator.Current;

          statFunction.Accumulate( ( from spn in statFunction.GetSourcePropertyNames()
                                     select dataItem.GetDataMemberValue( spn ) ).ToArray() );
        }

        return statFunction.GetResult();
      }
      catch( Exception e )
      {
        return new StatResult( e );
      }
    }

    private static IEnumerable<object> GetFilterGroupValues( IEnumerable<FilterGroupValue> values )
    {
      foreach( FilterGroupValue groupValue in values )
      {
        yield return groupValue.Value;
      }
    }

    private static IEnumerable<FilterGroupValue> CreateFilterGroupValues( IEnumerable<object> values )
    {
      foreach( object value in values )
      {
        yield return new FilterGroupValue( value );
      }
    }

    private CountQueryResult HandleRegularCountQuery( CountQueryParameters queryParameters )
    {
      lock( m_syncRoot )
      {
        // Get the appropriate index for the count query.
        bool reversedOrder;
        ListDataItemIndex index = this.GetIndex(
                                    queryParameters.Sort,
                                    queryParameters.Filter,
                                    true,
                                    out reversedOrder );

        long startInlineCount = index.ItemsCount;
        long endInlineCount = 0;

        // Find out the bounds of the filtered group.
        if( queryParameters.FilterGroup != null )
        {
          IEnumerable<object> jumpValues = ListDataSourceProvider.GetFilterGroupValues( queryParameters.FilterGroup.Values );

          // Get the number of items from the start of the group to the end of the source.
          ListDataItemEnumerable groupStartEnumerable = index.GetDataItems( jumpValues, reversedOrder, false );
          startInlineCount = groupStartEnumerable.InlineCount;

          // Get the number of items from the end of the group to the end of the source.
          ListDataItemEnumerable groupEndEnumerable = index.GetDataItems( jumpValues, reversedOrder, true );
          endInlineCount = groupEndEnumerable.InlineCount;
        }

        // Adjust the boundaries according to the desired starting position.
        if( queryParameters.Jump != null )
        {
          JumpRequest jumpRequest = queryParameters.Jump;
          JumpStartPosition startPosition = jumpRequest.StartPosition;
          bool includeStartingItem = ( startPosition == JumpStartPosition.Before );
          IEnumerable<object> jumpValues = ListDataSourceProvider.GetJumpValues( jumpRequest.Values );

          ListDataItemEnumerable enumerable = index.GetDataItems( jumpValues, reversedOrder, !includeStartingItem );
          int inlineCount = enumerable.InlineCount;

          if( inlineCount > endInlineCount )
          {
            startInlineCount = Math.Min( inlineCount, startInlineCount );
          }
          // The desired starting position is after the desired data range.
          else
          {
            startInlineCount = endInlineCount;
          }
        }

        long itemsCount = startInlineCount - endInlineCount;
        Debug.Assert( itemsCount >= 0 );

        return new CountQueryResult( itemsCount );
      }
    }

    private bool TryHandleSingleItemCountQuery( CountQueryParameters queryParameters, out CountQueryResult result )
    {
      result = null;

      Predicate<object> predicate;
      FilterExpressionBase filterExpression;
      ListDataSourceProvider.GetFilter( queryParameters.Filter, out predicate, out filterExpression );

      if( ( predicate != null )
        || ( filterExpression == null ) )
        return false;

      IEnumerable<object> values;

      // Find out if the filter is targeting a single item.
      if( !this.TryGetSingleItemPrimaryKeyValues( filterExpression, out values ) )
        return false;

      IEnumerable<JumpValue> itemValues = ListDataSourceProvider.CreateJumpValues( values ).ToArray();
      bool jumpAfterItem = false;

      if( queryParameters.FilterGroup != null )
      {
        IList<SortDescription> sortDescriptions = queryParameters.Sort.SortDescriptions;
        IList<FilterGroupValue> filterGroupValues = queryParameters.FilterGroup.Values.ToArray();
        List<object> groupValues = new List<object>();

        foreach( SortDescription pk in this.PrimaryKeyInfo )
        {
          bool found = false;

          for( int i = 0; !found && i < sortDescriptions.Count; i++ )
          {
            if( sortDescriptions[ i ].PropertyName == pk.PropertyName )
            {
              found = true;

              if( i >= filterGroupValues.Count )
                return false;

              groupValues.Add( filterGroupValues[ i ] );
            }
          }

          if( !found )
            return false;
        }

        if( !values.SequenceEqual( groupValues ) )
          return false;
      }
      else if( queryParameters.Jump != null )
      {
        if( !itemValues.SequenceEqual( queryParameters.Jump.Values ) )
          return false;

        jumpAfterItem = ( queryParameters.Jump.StartPosition == JumpStartPosition.After );
      }

      SortRequest sortRequest = new SortRequest( this.PrimaryKeyInfo );
      JumpRequest jumpBeforeItemRequest = new JumpRequest( itemValues, JumpStartPosition.Before );
      TakeRequest takeRequest = new TakeRequest( 1 );

      DataQueryParameters beforeItemParameters = new DataQueryParameters( takeRequest, null, sortRequest, null, null, jumpBeforeItemRequest );
      object expectedTargetItem = this.ExecuteDataQuery( beforeItemParameters ).Data.Cast<object>().SingleOrDefault();
      object unexpectedTargetItem = null;

      if( expectedTargetItem != null )
      {
        JumpRequest jumpAfterItemRequest = new JumpRequest( itemValues, JumpStartPosition.After );
        DataQueryParameters afterItemParameters = new DataQueryParameters( takeRequest, null, sortRequest, null, null, jumpAfterItemRequest );

        unexpectedTargetItem = this.ExecuteDataQuery( afterItemParameters ).Data.Cast<object>().SingleOrDefault();
      }

      // The expected item isn't in the data source anymore or has been skipped.
      if( ( jumpAfterItem )
        || ( expectedTargetItem == null )
        || ( object.Equals( expectedTargetItem, unexpectedTargetItem ) ) )
      {
        result = new CountQueryResult( 0 );
      }
      // The expected item was found.
      else
      {
        result = new CountQueryResult( 1 );
      }

      return true;
    }

    private DataQueryResult HandleRegularDataQuery( DataQueryParameters queryParameters )
    {
      SortRequest sortRequest = queryParameters.Sort;
      IEnumerable<SortDescription> sortOrder;

      if( sortRequest == null )
      {
        sortOrder = this.PrimaryKeyInfo;
        sortRequest = new SortRequest( sortOrder );
      }
      else
      {
        sortOrder = sortRequest.SortDescriptions;
      }

      lock( m_syncRoot )
      {
        // Get the appropriate index for the data query.
        bool reversedOrder;
        ListDataItemIndex index = this.GetIndex(
                                    sortRequest,
                                    queryParameters.Filter,
                                    false,
                                    out reversedOrder );

        // Get an enumerable that enumerates the items from the desired starting position.
        ListDataItemEnumerable enumerable = this.GetDataItems(
                                              queryParameters,
                                              index,
                                              sortOrder,
                                              reversedOrder );
        long inlineCount = enumerable.InlineCount;
        long totalCount = enumerable.TotalCount;

        // Skip and take only the desired items.
        IEnumerable<RawDataItem> dataItems = enumerable;
        dataItems = ListDataSourceProvider.Skip( dataItems, queryParameters.Skip, queryParameters.ItemJump );
        dataItems = ListDataSourceProvider.Take( dataItems, queryParameters.Take ).ToArray();

        return new DataQueryResult( dataItems, inlineCount, totalCount );
      }
    }

    private bool TryHandleSingleItemDataQuery( DataQueryParameters queryParameters, out DataQueryResult result )
    {
      result = null;

      Predicate<object> predicate;
      FilterExpressionBase filterExpression;
      ListDataSourceProvider.GetFilter( queryParameters.Filter, out predicate, out filterExpression );

      if( ( predicate != null )
        || ( filterExpression == null ) )
        return false;

      IEnumerable<object> values;

      // Find out if the filter is targeting a single item.
      if( !this.TryGetSingleItemPrimaryKeyValues( filterExpression, out values ) )
        return false;

      IEnumerable<JumpValue> itemValues = ListDataSourceProvider.CreateJumpValues( values ).ToArray();
      bool jumpAfterItem = false;

      if( queryParameters.ItemJump != null )
      {
        RawDataItem startingItem = ( RawDataItem )queryParameters.ItemJump.Item;

        if( !values.SequenceEqual( ( from pk in this.PrimaryKeyInfo
                                     select startingItem.GetDataMemberValue( pk.PropertyName ) ) ) )
          return false;
      }
      else if( queryParameters.Jump != null )
      {
        if( !itemValues.SequenceEqual( queryParameters.Jump.Values ) )
          return false;

        jumpAfterItem = ( queryParameters.Jump.StartPosition == JumpStartPosition.After );
      }

      SortRequest sortRequest = new SortRequest( this.PrimaryKeyInfo );
      JumpRequest jumpBeforeItemRequest = new JumpRequest( itemValues, JumpStartPosition.Before );
      TakeRequest takeRequest = new TakeRequest( 1 );

      DataQueryParameters beforeItemParameters = new DataQueryParameters( takeRequest, null, sortRequest, null, null, jumpBeforeItemRequest );
      object expectedTargetItem = this.ExecuteDataQuery( beforeItemParameters ).Data.Cast<object>().SingleOrDefault();
      object unexpectedTargetItem = null;

      if( expectedTargetItem != null )
      {
        JumpRequest jumpAfterItemRequest = new JumpRequest( itemValues, JumpStartPosition.After );
        DataQueryParameters afterItemParameters = new DataQueryParameters( takeRequest, null, sortRequest, null, null, jumpAfterItemRequest );

        unexpectedTargetItem = this.ExecuteDataQuery( afterItemParameters ).Data.Cast<object>().SingleOrDefault();
      }

      // The expected item isn't in the data source anymore.
      if( ( expectedTargetItem == null ) || ( object.Equals( expectedTargetItem, unexpectedTargetItem ) ) )
      {
        result = new DataQueryResult( Enumerable.Empty<object>(), 0, 0 );
      }
      // The expected item was found, but has been skipped or isn't wanted.
      else if( ( jumpAfterItem )
            || ( ( queryParameters.Skip != null ) && ( queryParameters.Skip.Count > 0 ) )
            || ( ( queryParameters.Take != null ) && ( queryParameters.Take.Count == 0 ) ) )
      {
        result = new DataQueryResult( Enumerable.Empty<object>(), 1, 1 );
      }
      // The expected item was found and must be returned.
      else
      {
        result = new DataQueryResult( new object[] { expectedTargetItem }, 1, 1 );
      }

      return true;
    }

    private GroupCountQueryResult HandleRegularGroupCountQuery( GroupCountQueryParameters queryParameters )
    {
      // There is no group count to return since there is no grouping at all.
      if( ( queryParameters.Sort == null ) || ( queryParameters.Sort.SortDescriptions.Count <= 0 ) )
        return new GroupCountQueryResult( Enumerable.Empty<long>() );

      lock( m_syncRoot )
      {
        // Get the appropriate index for the group count query.
        bool reversedOrder;
        ListDataItemIndex index = this.GetIndex(
                                    queryParameters.Sort,
                                    queryParameters.Filter,
                                    true,
                                    out reversedOrder );

        IEnumerable<long> groupCount = this.GetGroupCount(
                                         queryParameters.Jump,
                                         queryParameters.FilterGroup,
                                         index,
                                         queryParameters.Sort.SortDescriptions.Count,
                                         reversedOrder );

        return new GroupCountQueryResult( groupCount );
      }
    }

    private bool TryHandleSingleItemGroupCountQuery( GroupCountQueryParameters queryParameters, out GroupCountQueryResult result )
    {
      result = null;

      Predicate<object> predicate;
      FilterExpressionBase filterExpression;
      ListDataSourceProvider.GetFilter( queryParameters.Filter, out predicate, out filterExpression );

      if( ( predicate != null )
        || ( filterExpression == null ) )
        return false;

      IEnumerable<object> values;

      // Find out if the filter is targeting a single item.
      if( !this.TryGetSingleItemPrimaryKeyValues( filterExpression, out values ) )
        return false;

      IEnumerable<JumpValue> itemValues = ListDataSourceProvider.CreateJumpValues( values ).ToArray();
      bool jumpAfterItem = false;

      if( queryParameters.FilterGroup != null )
      {
        IList<SortDescription> sortDescriptions = queryParameters.Sort.SortDescriptions;
        IList<FilterGroupValue> filterGroupValues = queryParameters.FilterGroup.Values.ToArray();
        List<object> groupValues = new List<object>();

        foreach( SortDescription pk in this.PrimaryKeyInfo )
        {
          bool found = false;

          for( int i = 0; !found && i < sortDescriptions.Count; i++ )
          {
            if( sortDescriptions[ i ].PropertyName == pk.PropertyName )
            {
              found = true;

              if( i >= filterGroupValues.Count )
                return false;

              groupValues.Add( filterGroupValues[ i ] );
            }
          }

          if( !found )
            return false;
        }

        if( !values.SequenceEqual( groupValues ) )
          return false;
      }
      else if( queryParameters.Jump != null )
      {
        if( !itemValues.SequenceEqual( queryParameters.Jump.Values ) )
          return false;

        jumpAfterItem = ( queryParameters.Jump.StartPosition == JumpStartPosition.After );
      }

      SortRequest sortRequest = new SortRequest( this.PrimaryKeyInfo );
      JumpRequest jumpBeforeItemRequest = new JumpRequest( itemValues, JumpStartPosition.Before );
      TakeRequest takeRequest = new TakeRequest( 1 );

      DataQueryParameters beforeItemParameters = new DataQueryParameters( takeRequest, null, sortRequest, null, null, jumpBeforeItemRequest );
      object expectedTargetItem = this.ExecuteDataQuery( beforeItemParameters ).Data.Cast<object>().SingleOrDefault();
      object unexpectedTargetItem = null;

      if( expectedTargetItem != null )
      {
        JumpRequest jumpAfterItemRequest = new JumpRequest( itemValues, JumpStartPosition.After );
        DataQueryParameters afterItemParameters = new DataQueryParameters( takeRequest, null, sortRequest, null, null, jumpAfterItemRequest );

        unexpectedTargetItem = this.ExecuteDataQuery( afterItemParameters ).Data.Cast<object>().SingleOrDefault();
      }

      int groupCountDepth = queryParameters.Sort.SortDescriptions.Count;

      // The expected item isn't in the data source anymore, has been skipped or isn't wanted.
      if( ( jumpAfterItem )
        || ( expectedTargetItem == null )
        || ( object.Equals( expectedTargetItem, unexpectedTargetItem ) )
        || ( ( queryParameters.Skip != null ) && ( queryParameters.Skip.Count > 0 ) )
        || ( ( queryParameters.Take != null ) && ( queryParameters.Take.Count == 0 ) ) )
      {
        result = new GroupCountQueryResult( Enumerable.Repeat<long>( 0, groupCountDepth ) );
      }
      // The expected item was found and must be returned.
      else
      {
        result = new GroupCountQueryResult( Enumerable.Repeat<long>( 1, groupCountDepth ) );
      }

      return true;
    }

    private StatQueryResult HandleRegularStatQuery( StatQueryParameters queryParameters )
    {
      StatFunction statFunction = queryParameters.Function.StatFunction;
      StatResult statResult;

      // Find out if we may use the count query to give us the result quicker.
      CountFunction countFunction = statFunction as CountFunction;
      if( ( countFunction != null ) && ( countFunction.IncludeNullValues ) )
      {
        CountQueryResult countQueryResult = this.ExecuteCountQuery(
                                              new CountQueryParameters(
                                                queryParameters.Sort,
                                                queryParameters.Filter,
                                                null,
                                                queryParameters.FilterGroup ) );

        if( countQueryResult != null )
        {
          try
          {
            statResult = new StatResult( countQueryResult.Count );
            countFunction.AccumulateChildResult( statResult );
          }
          catch( Exception e )
          {
            statResult = new StatResult( e );
          }

          return new StatQueryResult( statResult );
        }
      }

      // Retrieve the values of the groups to keep.
      IList<object> filterGroupValues = null;
      if( queryParameters.FilterGroup != null )
      {
        filterGroupValues = ListDataSourceProvider.GetFilterGroupValues( queryParameters.FilterGroup.Values ).ToList();
      }

      lock( m_syncRoot )
      {
        // Get the appropriate index for the stat query.
        bool reversedOrder;
        ListDataItemIndex index = this.GetIndex(
                                    queryParameters.Sort,
                                    queryParameters.Filter,
                                    true,
                                    out reversedOrder );

        // Check out if the StatFunction has already been calculated earlier.
        statResult = index.GetStatValue( statFunction, filterGroupValues );

        // No value was found for the StatFunction.
        if( statResult == null )
        {
          ListDataItemEnumerable enumerable;
          long itemsCount;

          if( filterGroupValues != null )
          {
            enumerable = index.GetDataItems( filterGroupValues, reversedOrder, false );

            // Find out the number of items that are in the desired range.
            CountQueryResult countQueryResult = this.ExecuteCountQuery(
                                                  new CountQueryParameters(
                                                    queryParameters.Sort,
                                                    queryParameters.Filter,
                                                    null,
                                                    queryParameters.FilterGroup ) );

            itemsCount = countQueryResult.Count;
          }
          else
          {
            enumerable = index.GetDataItems( reversedOrder );
            itemsCount = enumerable.TotalCount;
          }

          // Calculate the StatFunction.
          statResult = ListDataSourceProvider.GetStatResult( statFunction, enumerable, itemsCount );

          // Keep the StatResult to reduce the calculation time next time.
          index.SetStatValue( statFunction, filterGroupValues, statResult );
        }

        return new StatQueryResult( statResult );
      }
    }

    private bool TryHandleSingleItemStatQuery( StatQueryParameters queryParameters, out StatQueryResult result )
    {
      result = null;

      Predicate<object> predicate;
      FilterExpressionBase filterExpression;
      ListDataSourceProvider.GetFilter( queryParameters.Filter, out predicate, out filterExpression );

      if( ( predicate != null )
        || ( filterExpression == null ) )
        return false;

      IEnumerable<object> values;

      // Find out if the filter is targeting a single item.
      if( !this.TryGetSingleItemPrimaryKeyValues( filterExpression, out values ) )
        return false;

      if( queryParameters.FilterGroup != null )
      {
        IEnumerable<object> groupValues = ListDataSourceProvider.GetFilterGroupValues( queryParameters.FilterGroup.Values );

        if( !groupValues.SequenceEqual( values ) )
          return false;
      }

      IEnumerable<FilterGroupValue> itemValues = ListDataSourceProvider.CreateFilterGroupValues( values ).ToArray();

      SortRequest sortRequest = new SortRequest( this.PrimaryKeyInfo );
      FilterGroupRequest filterGroupRequest = new FilterGroupRequest( itemValues );

      StatQueryParameters newQueryParameters = new StatQueryParameters(
                                                 queryParameters.Function,
                                                 sortRequest,
                                                 null,
                                                 filterGroupRequest );

      result = this.ExecuteStatQuery( newQueryParameters );

      return true;
    }

    private bool TryGetSingleItemPrimaryKeyValues( FilterExpressionBase filterExpression, out IEnumerable<object> values )
    {
      values = Enumerable.Empty<object>();

      SortDescription[] primaryKeys = this.PrimaryKeyInfo.ToArray();
      if( primaryKeys.Length == 0 )
        return false;

      if( primaryKeys.Length == 1 )
      {
        SortDescription primaryKey = primaryKeys.Single();
        FilterExpression target = filterExpression as FilterExpression;

        if( ( target == null )
          || ( target.FilterOperator != FilterOperator.Equal )
          || ( target.MemberName != primaryKey.PropertyName ) )
          return false;

        values = new object[] { target.Value };
      }
      else
      {
        FilterExpressionPreProcessor simplifier = new FilterExpressionPreProcessor( filterExpression, this );
        FilterExpressionPreProcessorResult simplifierResult = simplifier.GetResult();

        if( simplifierResult.Target != PreProcessResult.TargetSome )
          return false;

        AndFilterExpression target = simplifierResult.Expression as AndFilterExpression;

        if( ( target == null )
          || ( target.ChildExpressions.Count != primaryKeys.Length ) )
          return false;

        Dictionary<string, object> primaryKeyValues = new Dictionary<string, object>( primaryKeys.Length );

        // Make sure the expression has a single value for every field that makes the primary key.
        foreach( FilterExpressionBase childExpression in target.ChildExpressions )
        {
          FilterExpression childTarget = childExpression as FilterExpression;

          if( ( childTarget == null )
            || ( childTarget.FilterOperator != FilterOperator.Equal )
            || ( primaryKeyValues.ContainsKey( childTarget.MemberName ) )
            || ( !( from sd in primaryKeys
                    select sd.PropertyName ).Contains( childTarget.MemberName ) ) )
            return false;

          primaryKeyValues.Add( childTarget.MemberName, childTarget.Value );
        }

        values = ( from pk in primaryKeys
                   select primaryKeyValues[ pk.PropertyName ] ).ToArray();
      }

      return true;
    }

    private bool TryGetItem( object userObject, out RawDataItem dataItem )
    {
      dataItem = null;

      // Save us the time to look for the user object if it isn't of the expected type.
      if( ( userObject == null ) ||
          ( this.ElementType.IsAssignableFrom( userObject.GetType() ) ) )
      {
        lock( m_collection.SyncRoot )
        {
          dataItem = m_collection.FirstOrDefault( ( item ) => item.Data == userObject );
        }
      }

      return ( dataItem != null );
    }

    private void ClearIndexes()
    {
      // Clear all indexes to start from scratch on the next query.
      m_indexes.Clear();
    }

    private void AddDataItems( IEnumerable<RawDataItem> dataItems )
    {
      Action<ListDataItemIndex, RawDataItem> action =
        ( index, dataItem ) => index.Add( dataItem );

      this.ManageDataItems( dataItems, action );
    }

    private void RemoveDataItems( IEnumerable<RawDataItem> dataItems )
    {
      Action<ListDataItemIndex, RawDataItem> action =
        ( index, dataItem ) => index.Remove( dataItem );

      this.ManageDataItems( dataItems, action );
    }

    private void ManageDataItems(
      IEnumerable<RawDataItem> dataItems,
      Action<ListDataItemIndex, RawDataItem> action )
    {
      if( dataItems == null || action == null )
        return;

      foreach( ListDataItemIndex index in m_indexes )
      {
        index.ClearStatResults();

        foreach( RawDataItem dataItem in dataItems )
        {
          action.Invoke( index, dataItem );
        }
      }
    }

    private void OnItemsAdded( IEnumerable<RawDataItem> dataItems )
    {
      lock( m_syncRoot )
      {
        this.AddDataItems( dataItems );
      }

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs(
                                                DataSourceChangedAction.Add,
                                                dataItems.Cast<object>(),
                                                null );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsRemoved( IEnumerable<RawDataItem> dataItems )
    {
      lock( m_syncRoot )
      {
        this.RemoveDataItems( dataItems );
      }

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs(
                                                DataSourceChangedAction.Remove,
                                                null,
                                                dataItems.Cast<object>() );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsReplaced(
      IEnumerable<RawDataItem> newDataItems,
      IEnumerable<RawDataItem> oldDataItems )
    {
      lock( m_syncRoot )
      {
        this.RemoveDataItems( oldDataItems );
        this.AddDataItems( newDataItems );
      }

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs(
                                                DataSourceChangedAction.Replace,
                                                newDataItems.Cast<object>(),
                                                oldDataItems.Cast<object>() );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsReset()
    {
      lock( m_syncRoot )
      {
        // Clear all indexes and start from scratch on the next query.
        this.ClearIndexes();
      }

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs( DataSourceChangedAction.Reset );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnItemsChanged( IEnumerable<ItemChangedDescription> itemsChanged )
    {
      if( ( itemsChanged == null ) || ( !itemsChanged.Any() ) )
        return;

      lock( m_syncRoot )
      {
        foreach( ItemChangedDescription itemChanged in itemsChanged )
        {
          // Retrieve the targeted item.
          RawDataItem dataItem = ( RawDataItem )itemChanged.Item;

          // Refresh the indexes since the targeted item may have changed.
          RawDataItem[] dataItems = new RawDataItem[] { dataItem };

          this.RemoveDataItems( dataItems );
          this.AddDataItems( dataItems );
        }
      }

      DataSourceChangedEventArgs eventArgs = new DataSourceChangedEventArgs( itemsChanged );
      this.OnDataSourceChanged( eventArgs );
    }

    private void OnNotifyCollectionChanged( object sender, NotifyCollectionChangedEventArgs e )
    {
      if( e.Action == NotifyCollectionChangedAction.Add )
      {
        if( e.NewItems != null )
        {
          this.OnItemsAdded( e.NewItems.Cast<RawDataItem>() );
        }
      }
      else if( e.Action == NotifyCollectionChangedAction.Remove )
      {
        if( e.OldItems.Count > 0 )
        {
          this.OnItemsRemoved( e.OldItems.Cast<RawDataItem>() );
        }
      }
      else if( e.Action == NotifyCollectionChangedAction.Replace )
      {
        if( ( e.NewItems.Count > 0 ) && ( e.NewItems.Count == e.OldItems.Count ) )
        {
          this.OnItemsReplaced(
            e.NewItems.Cast<RawDataItem>(),
            e.OldItems.Cast<RawDataItem>() );
        }
      }
      else if( e.Action == NotifyCollectionChangedAction.Reset )
      {
        this.OnItemsReset();
      }
      else
      {
        throw new InvalidOperationException( "The received collection-changed action is not supported." );
      }
    }

    private void OnNotifyItemChanged( object sender, ItemChangedEventArgs e )
    {
      this.OnItemsChanged( e.ItemsChanged );
    }

    #region Private Fields

    private readonly IEnumerable m_originalDataSource; //null
    private readonly ListDataItemCollection m_collection; //null
    private readonly LinkedList<ListDataItemIndex> m_indexes = new LinkedList<ListDataItemIndex>();
    private readonly object m_syncRoot = new object();

    #endregion

    #region Private DefaultComparer Nested Type

    private class DefaultComparer : IComparer
    {
      public int Compare( object x, object y )
      {
        IComparable firstValue = ( IComparable )x;
        IComparable secondValue = ( IComparable )y;

        if( ( firstValue != null ) && ( secondValue != null ) )
        {
          return firstValue.CompareTo( secondValue );
        }
        else if( firstValue != null )
        {
          return 1;
        }
        else if( secondValue != null )
        {
          return -1;
        }
        else
        {
          return 0;
        }
      }
    }

    #endregion

    #region Private NullComparer Nested Type

    private class NullComparer : IComparer
    {
      internal NullComparer( IComparer comparer )
      {
        if( comparer == null )
          throw new ArgumentNullException( "comparer" );

        m_comparer = comparer;
      }

      public int Compare( object x, object y )
      {
        if( ( x != null ) && ( y != null ) )
          return m_comparer.Compare( x, y );

        if( x != null )
          return 1;

        if( y != null )
          return -1;

        return 0;
      }

      private IComparer m_comparer;
    }

    #endregion
  }
}
